#include "DynamicArray.h"

struct DynamicArray
{
    ElementType *array;//数组指针
    int capacity;//数组的容量
    int size;//元素个数
};

DArray *InitDArray()
{
    DArray *a = (DArray*)malloc(sizeof(DArray));
    if(a == NULL)
    {
        printf("InitDArray malloc error\n");
        exit(-1);
    }
    a->size = 0;
    a->capacity = 10;
    a->array = (ElementType*)malloc(sizeof(ElementType) * a->capacity);
    if(a->array == NULL)
    {
        printf("InitDArray array malloc error\n");
        exit(-1);
    }
    return a;
}

void InsertDArry(DArray *a, ElementType element)
{   
    if(a->size == a->capacity)
    {
        a->capacity *= 2;
        a->array = (ElementType*)realloc(a->array,a->capacity * sizeof(ElementType));
        if(a->array == NULL)
        {
            printf("InsertDArry realloc error\n");
            exit(-1);
        }
    }
    a->array[a->size++] = element; 
}
ElementType FindByElement(DArray *a,ElementType value,bool (*compare)(ElementType,ElementType))
{
    for(int i = 0;i < a->size;i++)
    {
        if(compare(a->array[i],value))
            return a->array[i];
    }
    return NULL;
}


ElementType RemoveByIndex(DArray *a,int index)
{
    ElementType result = a->array[index];
    for(int i = index;i < a->size - 1;i++)
    {
        a->array[i] = a->array[i + 1];
    }
    a->size--;
    return result;
}

ElementType RemoveByElement(DArray *a, ElementType value, bool (*compare)(ElementType, ElementType))
{
    for(int i = 0;i < a->size;i++)
    {
        if(compare(a->array[i],value))
            return RemoveByIndex(a,i);
    }
    return NULL;
}

void printDArray(DArray *a,void (*print)(ElementType))
{
    printf("capacity: %d   size: %d\n",a->capacity,a->size);
    for(int i = 0;i < a->size;i++)
        print(a->array[i]);
    printf("\n");
}

void MyFastSort(ElementType *a,int start,int end,bool (*compare)(ElementType,ElementType))
{
    if(start >= end)
        return;
    int left = start;
    int right = end;
    ElementType temp = a[start];
    while(left < right)
    {
       while(compare(a[right],temp) && left < right)
            right--;
        if(left < right)
            a[left++] = a[right];//把比基准值小的数放左边
        while(compare(temp,a[left]) && left < right)
            left++;
        if(left < right)
            a[right--] = a[left];//把比基准值大的数放右边
    }
    a[left] = temp;

    MyFastSort(a,start,left-1,compare);
    MyFastSort(a,right+1,end,compare);
}

void FastSort(DArray *a,bool (*compare)(ElementType,ElementType))
{
    MyFastSort(a->array,0,a->size - 1,compare);
}

ElementType BinarySearch(DArray *a, ElementType value, int (*compare)(ElementType, ElementType))
{
        int left = 0;
    int right = a->size -1;
    while(left <= right)
    {
        int mid = left + (right - left)/2;//((left & right) + (left ^ right)) >> 2
        if(compare(a->array[mid],value) == 0)
            return a->array[mid];
        else if(compare(a->array[mid],value) > 0)
            right = mid - 1;
        else if(compare(a->array[mid],value) < 0)
            left = mid + 1;
    }
    return NULL;
}

void ClearDArray(DArray *a, void (*clear)(ElementType))
{
    if(a != NULL)
    {
        for(int i = 0;i < a->size;i++)
            clear(a->array[i]);
        free(a->array);
        free(a);
    }
}

